import java.util.*;

public class Solution {
    /**
     * 287_寻找重复数
     *
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }

    public int findDuplicate_(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                return num;
            } else {
                set.add(num);
            }
        }
        return -1;
    }

    /**
     * 31_下一个排列
     */
    private void reverseArray(int[] array, int begin, int end) {
        while (begin < end) {
            int t = array[begin];
            array[begin] = array[end];
            array[end] = t;
            begin++;
            end--;
        }
    }

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        // 1.从后向前找到第一个递增序列
        int i = nums.length - 2, j = nums.length - 1, k = nums.length - 1, exchange = 0;
        while (nums[i] >= nums[j]) {
            i--;
            j--;
            if (i < 0) {
                reverseArray(nums, 0, nums.length - 1);
                return;
            }
        }
        // 2.从后向前找到第一个A[i]<A[k]
        while (k >= j) {
            if (nums[i] < nums[k]) break;
            k--;
        }
        // 3.交换A[i],A[k]
        exchange = nums[i];
        nums[i] = nums[k];
        nums[k] = exchange;
        reverseArray(nums, j, nums.length - 1);
    }

    /**
     * 75_颜色分类
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        int ptr = 0, exchange = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                exchange = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = exchange;
                ptr++;
            }
        }
        for (int i = ptr; i < nums.length; i++) {
            if (nums[i] == 1) {
                exchange = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = exchange;
                ptr++;
            }
        }
    }

    /**
     * 169_多数元素
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int candidate = nums[0], count = 0;
        for (int num : nums) {
            if (num == candidate) count++;
            else {
                count--;
                if (count == 0) {
                    candidate = num;
                    count = 1;
                }
            }
        }
        return candidate;
    }

    /**
     * 136_只出现一次的元素
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

    /**
     * 72_编辑距离
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        if (word1.equals(word2)) return 0;
        if (word1.isEmpty()) return word2.length();
        if (word2.isEmpty()) return word1.length();
        int[][] d = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i <= word1.length(); i++) {
            d[i][0] = i;
        }
        for (int j = 0; j <= word2.length(); j++) {
            d[0][j] = j;
        }
        if (word1.charAt(0) == word2.charAt(0)) {
            d[1][1] = 0;
        } else {
            d[1][1] = 1;
        }
        for (int i = 1; i <= word1.length(); i++) {
            char c = word1.charAt(i - 1);
            for (int j = 1; j <= word2.length(); j++) {
                if (c == word2.charAt(j - 1)) {
                    d[i][j] = d[i - 1][j - 1];
                } else {
                    d[i][j] = Math.min(d[i][j - 1] + 1, Math.min(d[i - 1][j] + 1, d[i - 1][j - 1] + 1));
                }
            }
        }
        return d[word1.length()][word2.length()];
    }

    /**
     * 最长公共子序列
     *
     * @param text1
     * @param text2
     * @return
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] d = new int[text1.length() + 1][text2.length() + 1];
        if (text1.equals(text2)) return text1.length();
        if (text1.isEmpty() || text2.isEmpty()) return 0;
        d[0][0] = 0;
        for (int i = 0; i <= text1.length(); i++) {
            d[i][0] = 0;
        }
        for (int j = 0; j <= text2.length(); j++) {
            d[0][j] = 0;
        }
        for (int i = 1; i <= text1.length(); i++) {
            char c = text1.charAt(i - 1);
            for (int j = 1; j <= text2.length(); j++) {
                if (c == text2.charAt(j - 1)) {
                    d[i][j] = d[i - 1][j - 1] + 1;
                } else {
                    d[i][j] = Math.max(d[i - 1][j], Math.max(d[i][j - 1], d[i - 1][j - 1]));
                }
            }
        }
        return d[text1.length()][text2.length()];
    }

    /**
     * 5_最长回文子串
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s.length() < 2) return s;
        int maxLen = 1;
        int begin = 0;
        int[][] d = new int[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            d[i][i] = 1;
        }
        for (int j = 1; j < s.length(); j++) {
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) {
                    d[i][j] = 0;
                } else if (j - i < 3) {
                    d[i][j] = 1;
                } else {
                    d[i][j] = d[i + 1][j - 1];
                }
                if (d[i][j] == 1 && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substring(begin, begin + maxLen);
    }

    /**
     * 64_最小路径和
     *
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] dp = new int[rows][cols];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < cols; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][cols - 1];
    }

    /**
     * 62_不同路径
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for (int i = 1; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 32_最长有效括号
     *
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int maxLen = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                dp[i] = 0;
            } else {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }


    /**
     * 416_分割等和子集
     *
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        if (Arrays.stream(nums).sum() % 2 == 1) return false;
        int capacity = Arrays.stream(nums).sum() / 2;
        int[][] dp = new int[nums.length][capacity + 1];
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < capacity + 1; i++) {
            if (i >= nums[0]) dp[0][i] = nums[0];
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j < capacity + 1; j++) {
                // 背包放不下物品
                if (nums[i] > j) dp[i][j] = dp[i - 1][j];
                    // 背包放的下，选择放与不放
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }
            }
        }
        return dp[nums.length - 1][capacity] == capacity;
    }

    /**
     * 152_乘积最大子数组
     *
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int[] max = new int[nums.length];
        int[] min = new int[nums.length];
        max[0] = nums[0];
        min[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            min[i] = Math.min(nums[i], Math.min(max[i - 1] * nums[i], min[i - 1] * nums[i]));
            max[i] = Math.max(nums[i], Math.max(nums[i] * min[i - 1], nums[i] * max[i - 1]));
        }
        return Arrays.stream(max).max().getAsInt();
    }

    /**
     * 300_最长递增子序列
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxLen = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    /**
     * 139_单词拆分
     *
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        HashSet<String> set = new HashSet<>(wordDict);
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * 322_零钱兑换
     *
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        // dp[i]定义为组成金额为i需要的最少硬币数量
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] <= amount ? dp[amount] : -1;
    }

    /**
     * 279_完全平方数
     *
     * @param n
     * @return
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }

    /**
     * 198_打家劫舍
     *
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    /**
     * 118_杨辉三角
     *
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }

    /**
     * 70_爬楼梯
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int[] dp = new int[50];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 763_划分字母区间
     *
     * @param s
     * @return
     */
    public List<Integer> partitionLabels(String s) {
        // 首先记录每一个字母最后出现的位置
        int[] last = new int[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        List<Integer> res = new ArrayList<>();
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            end = Math.max(end, last[s.charAt(i) - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }

    /**
     * 45_跳跃游戏Ⅱ
     *
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int position = nums.length - 1;
        int step = 0;
        while (position != 0) {
            for (int i = 0; i < position; i++) {
                if (nums[i] + i >= position) {
                    step++;
                    position = i;
                    break;
                }
            }
        }
        return step;
    }

    /**
     * 55_跳跃游戏
     *
     * @param nums
     * @return
     */
    public boolean canJump(int[] nums) {
        int cover = 0;
        if (nums.length == 1) return true;
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(cover, nums[i] + i);
            if (cover >= nums.length - 1) return true;
        }
        return false;
    }

    /**
     * 121_买卖股票的最佳时机
     *
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int res = 0;
        int minPrice = prices[0];
        for (int price : prices) {
            res = Math.max(res, price - minPrice);
            minPrice = Math.min(minPrice, price);
        }
        return res;
    }

    /**
     * 295_数据流的中位数
     */
    class MedianFinder {
        PriorityQueue<Integer> minHeap;
        PriorityQueue<Integer> maxHeap;

        public MedianFinder() {
            minHeap = new PriorityQueue<>();
            maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
        }

        public void addNum(int num) {
            if (minHeap.size() == maxHeap.size()) {
                maxHeap.add(num);
                minHeap.add(maxHeap.poll());
            } else {
                minHeap.add(num);
                maxHeap.add(minHeap.poll());
            }
        }

        public double findMedian() {
            if (minHeap.size() != maxHeap.size()) {
                return minHeap.peek();
            } else {
                return (minHeap.peek() + maxHeap.peek()) / 2.0;
            }
        }
    }

    /**
     * 347_前k个高频元素
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (heap.size() < k) {
                heap.add(new int[]{num, count});
            } else {
                if (heap.peek()[1] < count) {
                    heap.poll();
                    heap.add(new int[]{num, count});
                }
            }
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = heap.poll()[0];
        }
        return res;
    }

    /**
     * 215_数组的第k大元素
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(k);
        for (int i = 0; i < k; i++) {
            heap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap.peek()) {
                heap.poll();
                heap.offer(nums[i]);
            }
        }
        return heap.peek();
    }

    /**
     * 20_有效的括号
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        if (s.length() % 2 == 1) return false;
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if (s.charAt(i) == '{' || s.charAt(i) == '(' || s.charAt(i) == '[') {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty()) return false;
                Character left = stack.pop();
                if (s.charAt(i) == '}' && left != '{') return false;
                if (s.charAt(i) == ']' && left != '[') return false;
                if (s.charAt(i) == ')' && left != '(') return false;
            }
        }
        return stack.isEmpty();
    }

    /**
     * 155_最小栈
     */
    class MinStack {
        Stack<int[]> minStack;

        public MinStack() {
            minStack = new Stack<>();
        }

        public void push(int val) {
            if (minStack.isEmpty()) {
                minStack.push(new int[]{val, val});
            } else {
                minStack.push(new int[]{val, Math.min(val, getMin())});
            }
        }

        public void pop() {
            minStack.pop();
        }

        public int top() {
            return minStack.peek()[0];
        }

        public int getMin() {
            return minStack.peek()[1];
        }
    }


    /**
     * 394_字符串解码
     *
     * @param s
     * @return
     */
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        Stack<Integer> stack_multi = new Stack<>();
        Stack<String> stack_res = new Stack<>();
        int multi = 0;
        for (Character c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                multi = multi * 10 + Integer.parseInt(c + "");
            } else if (Character.isLetter(c)) {
                res.append(c);
            } else if (c == '[') {
                stack_res.push(res.toString());
                stack_multi.push(multi);
                res.setLength(0);
                multi = 0;
            } else if (c == ']') {
                int count = stack_multi.pop();
                StringBuilder builder = new StringBuilder(stack_res.pop());
                for (int i = 0; i < count; i++) {
                    builder.append(res);
                }
                res = new StringBuilder(builder);
            }
        }
        return res.toString();
    }

    /**
     * 739_每日温度
     * 单调栈
     * [73,74,75,71,69,72,76,73]
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temperatures.length; i++) {
            int temperature = temperatures[i];
            while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
                res[stack.peek()] = i - stack.pop();
            }
            stack.push(i);
        }
        return res;
    }

    /**
     * 84_柱状图最大矩形
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            int current = heights[i];
            while (!stack.isEmpty() && current <= heights[stack.peek()]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = heights.length - 1; i >= 0; i--) {
            int current = heights[i];
            while (!stack.isEmpty() && current <= heights[stack.peek()]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? heights.length : stack.peek();
            stack.push(i);
        }
        int res = 0;
        for (int i = 0; i < heights.length; i++) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }

    /**
     * 35_搜索插入位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 74_搜索二维矩阵
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0, right = matrix.length * matrix[0].length - 1;
        int cols = matrix[0].length;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int val = matrix[mid / cols][mid % cols];
            if (val == target) return true;
            else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }

    /**
     * 34_在排序数组中查找元素的第一个和最后一个位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int left = -1, right = -1;
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] < target) {
                i = mid + 1;
            } else if (nums[mid] > target) {
                j = mid - 1;
            } else {
                right = mid;
                i = mid + 1;
            }
        }
        i = 0;
        j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) / 2;
            if (nums[mid] < target) {
                i = mid + 1;
            } else if (nums[mid] > target) {
                j = mid - 1;
            } else {
                left = mid;
                j = mid - 1;
            }
        }
        return new int[]{left, right};
    }

    /**
     * 33_搜索排序旋转数组
     *
     * @param nums
     * @param target
     * @return
     */
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target <= nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (nums[mid] <= target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    /**
     * 153_寻找排序数组中的最小值
     *
     * @param nums
     * @return
     */
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[left] <= nums[mid] && nums[mid] <= nums[right]) {
                return nums[left];
            } else if (nums[mid] >= nums[left]) {
                left = mid + 1;
            } else if (nums[mid] <= nums[right]) {
                right = mid;
            }
        }
        return nums[left];
    }

    /**
     * 4_寻找两个正序数组的中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {
            return getKthElement(nums1, nums2, totalLength / 2 + 1);
        } else {
            return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;
        while (true) {
            if (index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }

    /**
     * 46_全排列
     */
    class permute {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> path = Arrays.asList(new Integer[nums.length]);
            boolean[] onPath = new boolean[nums.length];
            dfs(0, nums, res, path, onPath);
            return res;
        }

        private void dfs(int i, int[] nums, List<List<Integer>> res, List<Integer> path, boolean[] onPath) {
            if (i == nums.length) {
                res.add(new ArrayList<>(path));
            } else {
                for (int j = 0; j < nums.length; j++) {
                    if (!onPath[j]) {
                        path.set(i, nums[j]);
                        onPath[j] = true;
                        dfs(i + 1, nums, res, path, onPath);
                        onPath[j] = false;
                    }
                }
            }
        }
    }

    /**
     * 78_子集
     */
    class subsets {
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            dfs(0, nums, res, path);
            return res;
        }

        private void dfs(int i, int[] nums, List<List<Integer>> res, List<Integer> path) {
            if (i == nums.length) {
                res.add(new ArrayList<>(path));
            } else {
                // 不选 i
                dfs(i + 1, nums, res, path);
                // 选 i
                path.add(nums[i]);
                dfs(i + 1, nums, res, path);
                path.removeLast();
            }
        }
    }

    /**
     * 17_电话号码的字母组合
     */
    class letterCombinations {
        public List<String> letterCombinations(String digits) {
            List<String> combinations = new ArrayList<>();
            if (digits.isEmpty()) {
                return combinations;
            }
            Map<Character, String> phoneMap = new HashMap<>() {{
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
            return combinations;
        }

        public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
            if (index == digits.length()) {
                combinations.add(combination.toString());
            } else {
                char digit = digits.charAt(index);
                String letters = phoneMap.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
                    combination.append(letters.charAt(i));
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }
    }

    /**
     * 1_两数之和
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) return new int[]{map.get(target - nums[i]), i};
            else {
                map.put(nums[i], i);
            }
        }
        return new int[]{-1, -1};
    }

    /**
     * 49_字母异位词分组
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> res = new HashMap<>();
        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);
            if (res.containsKey(new String(charArray))) {
                res.get(new String(charArray)).add(str);
            } else {
                List<String> t = new ArrayList<>();
                t.add(str);
                res.put(new String(charArray), t);
            }
        }
        return new ArrayList<>(res.values());
    }


    /**
     * 128_最长连续序列
     *
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for (int x : set) {
            if (set.contains(x - 1)) continue;
            int y = x + 1;
            while (set.contains(y)) y++;
            ans = Math.max(ans, y - x);
        }
        return ans;
    }

    /**
     * 283_移动零
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int pointer = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[pointer++] = nums[i];
            }
        }

        for (int i = pointer; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    /**
     * 11_盛水最多的容器
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            int area = Math.min(height[left], height[right]) * (right - left);
            res = Math.max(res, area);
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }

    /**
     * 15_三数之和
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) continue;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.add(List.of(nums[i], nums[j], nums[k]));
                    k--;
                    j++;
                    while (j < k && nums[k] == nums[k + 1]) k--;
                    while (j < k && nums[j] == nums[j - 1]) j++;
                } else if (sum > 0) {
                    k--;
                    while (j < k && nums[k] == nums[k + 1]) k--;
                } else {
                    j++;
                    while (j < k && nums[j] == nums[j - 1]) j++;
                }
            }
        }
        return res;
    }

    /**
     * 42_接雨水
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int sum = 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];
        for (int i = 1; i <= height.length - 2; i++) {
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(height[i + 1], max_right[i + 1]);
        }

        for (int i = 1; i <= height.length - 2; i++) {
            int min = Math.min(max_left[i], max_right[i]);
            if (height[i] < min) {
                sum += min - height[i];
            }
        }
        return sum;
    }

    /**
     * 3_无重复字符的最长子串
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        Set<Character> set = new HashSet<>();
        for (int left = 0, right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            while (set.contains(ch)) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(ch);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    /**
     * 438_字符串中的所有字母异味词
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        int[] count_S = new int[26];
        int[] count_P = new int[26];
        for (char c : p.toCharArray()) {
            count_P[c - 'a']++;
        }
        for (int right = 0; right < s.length(); right++) {
            count_S[s.charAt(right) - 'a']++;
            int left = right - p.length() + 1;
            if (left < 0) continue;
            if (Arrays.equals(count_P, count_S)) {
                res.add(left);
            }
            count_S[s.charAt(left) - 'a']--;
        }
        return res;
    }

    /**
     * 560_和为k的子数组
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 初始化前缀和为0的次数为1
        for (int num : nums) {
            sum += num;
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    /**
     * 239_滑动窗口最大值
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        // 维护一个单调递减的队列
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            // 入队
            while (!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
            // 出队
            if (i - deque.getFirst() >= k) { // 队首已经离开窗口了
                deque.removeFirst();
            }
            if (i >= k - 1) {
                res[i - k + 1] = nums[deque.getFirst()];
            }
        }
        return res;
    }

    /**
     * 76_最小覆盖子串
     *
     * @param s
     * @param t
     * @return
     */
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();

        // 初始化 need，记录 t 中每个字符的出现次数
        for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);

        int left = 0, right = 0; // 窗口的左右边界
        int valid = 0; // 已经匹配上的字符数量
        int start = 0, minLen = Integer.MAX_VALUE; // 最小窗口的起始位置和长度

        while (right < s.length()) {
            char r = s.charAt(right);
            right++;

            // 更新窗口内字符的计数
            if (need.containsKey(r)) {
                window.put(r, window.getOrDefault(r, 0) + 1);
                if (window.get(r).equals(need.get(r))) valid++;
            }

            // 当窗口内的字符已经完全包含了 t 中的所有字符时
            while (valid == need.size()) {
                // 更新最小窗口的起始位置和长度
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char l = s.charAt(left);
                // 缩小窗口，移动左边界
                if (need.containsKey(l)) {
                    window.put(l, window.get(l) - 1);
                    if (window.get(l) < need.get(l)) valid--;
                }
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }

    /**
     * 53_最大子数组和
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    /**
     * 56_合并区间
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            else return a[1] - b[1];
        });
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= intervals[i - 1][1]) {
                intervals[i][0] = intervals[i - 1][0];
                if (intervals[i][1] < intervals[i - 1][1]) {
                    intervals[i][1] = intervals[i - 1][1];
                }
            } else if (intervals[i][0] > intervals[i - 1][1]) {
                res.add(new int[]{intervals[i - 1][0], intervals[i - 1][1]});
            }
        }
        res.add(new int[]{intervals[intervals.length - 1][0], intervals[intervals.length - 1][1]});
        return res.toArray(new int[0][]);
    }

    /**
     * 189_轮转数组
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse_189(nums, nums.length - k, nums.length - 1);
        reverse_189(nums, 0, nums.length - k - 1);
        reverse_189(nums, 0, nums.length - 1);
    }

    private void reverse_189(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    /**
     * 238_除自身以外数组的乘积
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length], pre = new int[nums.length], suf = new int[nums.length];
        pre[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        suf[nums.length - 1] = 1;
        for (int j = nums.length - 2; j >= 0; j--) {
            suf[j] = suf[j + 1] * nums[j + 1];
        }
        for (int k = 0; k < nums.length; k++) {
            res[k] = pre[k] * suf[k];
        }
        return res;
    }

    /**
     * 41_缺失的第一个正数
     *
     * @param nums
     * @return
     */
    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
                swap_41(nums, i, nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    private void swap_41(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }


    /**
     * 73_矩阵置零
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        int[] row = new int[matrix.length];
        int[] col = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row[i] = -1;
                    col[j] = -1;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (row[i] == -1 || col[j] == -1) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    /**
     * 54_螺旋矩阵
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        int count = matrix.length * matrix[0].length;
        int directionIndex = 0;
        int[][] direction = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        int rows = matrix.length, cols = matrix[0].length, row = 0, col = 0;
        for (int i = 0; i < count; i++) {
            res.add(matrix[row][col]);
            visited[row][col] = true;
            int nextRow = row + direction[directionIndex][0];
            int nextCol = col + direction[directionIndex][1];
            if (nextRow < 0 || nextRow > rows - 1 || nextCol < 0 || nextCol > cols - 1 || visited[nextRow][nextCol]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row = row + direction[directionIndex][0];
            col = col + direction[directionIndex][1];
        }
        return res;
    }

    /**
     * 48_旋转矩阵
     *
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        /**
         * 上下对称: matrix[i][j] = matrix[n-i-1][j]
         * 左右对称: matrix[i][j] = matrix[i][n-j-1]
         * 主对角线对称: matrix[i][j] = matrix[j][i]
         * 副对角线对称: matrix[i][j] = matrix[n-j-1][n-i-1]
         * 旋转90度: matrix[i][j] = matrix[j][n-i-1]
         *       相当于 matrix[i][j]--> matrix[j][i] --> matrix[j][n-i-1]
         */

        // 主对角线对称
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 左右对称
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][matrix.length - j - 1];
                matrix[i][matrix.length - j - 1] = temp;
            }
        }
    }

    /**
     * 240_搜索二维矩阵Ⅱ
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix_(int[][] matrix, int target) {
        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) return true;
            else if (matrix[i][j] < target) {
                i++;
            } else if (matrix[i][j] > target) {
                j--;
            }
        }
        return false;
    }

    /**
     * 160_相交链表
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA, q = headB;
        while (p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        return p;
    }

    /**
     * 19_删除链表的倒数第N个节点
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy, right = dummy;
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        while (right.next != null) {
            left = left.next;
            right = right.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }

    /**
     * 206_翻转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }

    /**
     * 234_回文链表
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode mid = middleNode(head);
        ListNode head2 = reverseList(mid);
        while (head2 != null) {
            if (head.val != head2.val) return false;
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }

    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 141_环形链表
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) return true;
        }
        return false;
    }

    /**
     * 142_环形链表Ⅱ
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                fast = head;
                while (fast != slow) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    /**
     * 21_合并两个有序链表
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        current.next = list1 != null ? list1 : list2;
        return dummy.next;
    }

    /**
     * 2_两数相加
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            if (l1 != null) {
                carry += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                carry += l2.val;
                l2 = l2.next;
            }
            current.next = new ListNode(carry % 10);
            current = current.next;
            carry /= 10;
        }
        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 24_两两交换链表中的节点
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode node0 = dummy, node1 = head;
        while (node1 != null && node1.next != null) {
            ListNode node2 = node1.next, node3 = node2.next;
            node0.next = node2;
            node2.next = node1;
            node1.next = node3;
            node0 = node1;
            node1 = node3;
        }
        return dummy.next;
    }

    /**
     * 25_k个一组翻转链表
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计节点个数
        int size = 0;
        for (ListNode current = head; current != null; current = current.next) {
            size++;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode current = head;
        ListNode pre = null;
        ListNode pointer = dummy;
        for (; size >= k; size -= k) {
            // k个一组翻转链表
            for (int i = 0; i < k; i++) {
                ListNode next = current.next;
                current.next = pre;
                pre = current;
                current = next;
            }
            ListNode next = pointer.next;
            pointer.next.next = current;
            pointer.next = pre;
            pointer = next;
        }
        return dummy.next;
    }

    /**
     * 138_随机链表的复制
     *
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if (head == null) return head;
        Map<Node, Node> map = new HashMap<>();
        Node current = head;
        // 第一次遍历，创建新节点并映射
        while (current != null) {
            map.put(current, new Node(current.val));
            current = current.next;
        }
        current = head;
        // 第二次遍历，设置next与random指针
        while (current != null) {
            Node clone = map.get(current);
            clone.next = map.get(current.next);
            clone.random = map.get(current.random);
            current = current.next;
        }
        return map.get(head);
    }

    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    /**
     * 148_排序链表
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode head2 = middleNode_148(head);
        head2 = sortList(head2);
        head = sortList(head);
        return mergeTwoLists_148(head, head2);
    }

    private ListNode middleNode_148(ListNode head) {
        ListNode pre = head, slow = head, fast = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        return slow;
    }

    private ListNode mergeTwoLists_148(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), cur = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummy.next;
    }

    /**
     * 23_合并k个升序链表
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) {
                priorityQueue.offer(head);
            }
        }
        ListNode dummy = new ListNode(0), cur = dummy;
        while (!priorityQueue.isEmpty()) {
            ListNode node = priorityQueue.poll();
            if (node.next != null) priorityQueue.offer(node.next);
            cur.next = node;
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 94_二叉树的中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    private void inorder(TreeNode root, List<Integer> list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }

    /**
     * 146_LRU缓存
     */
    class LRUCache {

        private final int capacity;
        private final Node dummy = new Node(0, 0);
        private Map<Integer, Node> keyToNode = new HashMap<>();

        public LRUCache(int capacity) {
            this.capacity = capacity;
            dummy.prev = dummy;
            dummy.next = dummy;
        }

        public int get(int key) {
            Node node = getNode(key);
            return node == null ? -1 : node.value;
        }

        private Node getNode(int key) {
            if (!keyToNode.containsKey(key)) return null;
            Node node = keyToNode.get(key);
            remove(node);
            pushFront(node);
            return node;
        }

        private void pushFront(Node node) {
            node.prev = dummy;
            node.next = dummy.next;
            node.prev.next = node;
            node.next.prev = node;
        }

        private void remove(Node node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
        }

        public void put(int key, int value) {
            Node node = getNode(key);
            if (node != null) {
                node.value = value;
                return;
            }
            node = new Node(key, value);
            keyToNode.put(key, node);
            pushFront(node);
            if (keyToNode.size() > capacity) {
                Node back = dummy.prev;
                keyToNode.remove(back.key);
                remove(back);
            }
        }

        private static class Node {
            int key, value;
            Node prev, next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 104_二叉树的最大深度
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }

    /**
     * 226_翻转二叉树
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }

    private boolean func(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return func(left.left, right.right) && func(left.right, right.left);
    }

    /**
     * 101_对称二叉树
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return func(root.left, root.right);
    }

    /**
     * 543_二叉树的最大直径
     *
     * @param root
     * @return
     */
    private int ans_543 = 1;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs_543(root);
        return ans_543 - 1;
    }

    private int dfs_543(TreeNode root) {
        if (root == null) return 0;
        int L = dfs_543(root.left);
        int R = dfs_543(root.right);
        ans_543 = Math.max(ans_543, L + R + 1);
        return Math.max(L, R) + 1;
    }

    /**
     * 102_二叉树的层次遍历
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            List<Integer> list = new ArrayList<>();
            while (size != 0) {
                TreeNode node = deque.poll();
                list.add(node.val);
                if (node.left != null) {
                    deque.offer(node.left);
                }
                if (node.right != null) {
                    deque.offer(node.right);
                }
                size--;
            }
            res.add(list);
        }
        return res;
    }

    /**
     * 108_有序数组转化内二叉搜索树
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return insert_108(nums, 0, nums.length - 1);
    }

    private TreeNode insert_108(int[] nums, int left, int right) {
        if (left > right) return null;
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = insert_108(nums, left, mid - 1);
        root.right = insert_108(nums, mid + 1, right);
        return root;
    }

    /**
     * 98_验证二叉搜索树
     *
     * @param root
     * @return
     */
    private Long pre_98 = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (root.val <= pre_98) return false;
        pre_98 = (long) root.val;
        return !isValidBST(root.right);
    }

    /**
     * 230_二叉树搜索树的第k小元素
     *
     * @param root
     * @param k
     * @return
     */
    private int ans_230, k_230;

    public int kthSmallest(TreeNode root, int k) {
        this.k_230 = k;
        inOrder_230(root);
        return ans_230;
    }

    private void inOrder_230(TreeNode root) {
        if (root == null) return;
        inOrder_230(root.left);
        if (this.k_230 == 1) this.ans_230 = root.val;
        this.k_230--;
        inOrder_230(root.right);
    }

    /**
     * 199_二叉树的右视图
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Order_199(root, 0, res);
        return res;
    }

    public void Order_199(TreeNode root, int depth, List<Integer> res) {
        if (root == null) return;
        if (depth == res.size()) {
            res.add(root.val);
        }
        Order_199(root.right, depth + 1, res);
        Order_199(root.left, depth + 1, res);
    }

    /**
     * 114_二叉树转化为链表
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        preOrder_114(root, list);
        for (int i = 1; i < list.size(); i++) {
            TreeNode prev = list.get(i - 1), cur = list.get(i);
            prev.left = null;
            prev.right = cur;
        }
    }

    private void preOrder_114(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        list.add(root);
        preOrder_114(root.left, list);
        preOrder_114(root.right, list);
    }

    /**
     * 105_从前序与中序遍历序列构建二叉树
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> index = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            index.put(inorder[i], i);
        }
        return dfs_105(preorder, 0, preorder.length, 0, inorder.length, index);
    }

    /*
        preOrder [3,9,20,15,7]
        inOrder  [9,3,15,20,7]    
     */
    private TreeNode dfs_105(int[] preorder, int preL, int preR, int inL, int inR, Map<Integer, Integer> index) {
        if (preL == preR) return null;
        // 左子树的大小
        int leftSize = index.get(preorder[preL]) - inL;
        TreeNode left = dfs_105(preorder, preL + 1, preL + leftSize + 1, inL, inL + leftSize, index);
        TreeNode right = dfs_105(preorder, preL + leftSize + 1, preR, inL + leftSize + 1, inR, index);
        return new TreeNode(preorder[preL], left, right);
    }

    /**
     * 437_路径总和Ⅲ
     *
     * @param root
     * @param targetSum
     * @return
     */
    private int ans_437;

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> count = new HashMap<>();
        count.put(0L, 1);
        dfs_437(root, 0, targetSum, count);
        return ans_437;
    }

    private void dfs_437(TreeNode node, long s, int targetSum, Map<Long, Integer> count) {
        if (node == null) return;
        s += node.val;
        ans_437 += count.getOrDefault(s - targetSum, 0);
        count.merge(s, 1, Integer::sum);
        dfs_437(node.left, s, targetSum, count);
        dfs_437(node.right, s, targetSum, count);
        count.merge(s, -1, Integer::sum);
    }

    /**
     * 236_二叉树的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) { // 左右都找到
            return root; // 当前节点是最近公共祖先
        }
        return left != null ? left : right;
    }

    /**
     * 124_二叉树中的最大路径和
     *
     * @param root
     * @return
     */
    private int ans_124 = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs_124(root);
        return ans_124;
    }

    public int dfs_124(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftGain = Math.max(dfs_124(node.left), 0);
        int rightGain = Math.max(dfs_124(node.right), 0);
        int price = node.val + leftGain + rightGain;
        ans_124 = Math.max(ans_124, price);
        return node.val + Math.max(leftGain, rightGain);
    }

    /**
     * 200_岛屿数量
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        if (grid == null) return 0;
        int rows = grid.length;
        int cols = grid[0].length;
        int res = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    res++;
                    dfs_200(grid, i, j);
                }
            }
        }

        return res;
    }

    private void dfs_200(char[][] grid, int r, int c) {
        int rows = grid.length, cols = grid[0].length;
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
        grid[r][c] = '0';
        dfs_200(grid, r - 1, c);
        dfs_200(grid, r + 1, c);
        dfs_200(grid, r, c - 1);
        dfs_200(grid, r, c + 1);

    }

    /**
     * 994_腐烂的橘子
     *
     * @param grid
     * @return
     */
    private static final int[][] DIRECTIONS_994 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向

    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int fresh = 0;
        List<int[]> q = new ArrayList<>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {
                    fresh++;
                } else if (grid[i][j] == 2) {
                    q.add(new int[]{i, j});
                }
            }
        }
        int ans = 0;
        while (fresh > 0 && !q.isEmpty()) {
            ans++; // 经过一分钟
            List<int[]> temp = q;
            q = new ArrayList<>();
            // 遍历所有腐烂的橘子
            for (int[] pos : temp) {
                for (int[] direction : DIRECTIONS_994) {
                    int i = pos[0] + direction[0];
                    int j = pos[1] + direction[1];
                    if (i >= 0 && j >= 0 && i < rows && j < cols && grid[i][j] == 1) {
                        fresh--;
                        grid[i][j] = 2;
                        q.add(new int[]{i, j});
                    }
                }
            }
        }
        return fresh > 0 ? -1 : ans;
    }

    /**
     * 207_课程表
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < prerequisites.length; i++) {
            inDegree[prerequisites[i][0]]++;
            map.putIfAbsent(prerequisites[i][1], new ArrayList<>());
            map.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) deque.offer(i);
        }

        while (!deque.isEmpty()) {
            int course = deque.poll();
            numCourses--;
            for (Integer nextCourse : map.getOrDefault(course, new ArrayList<>())) {
                inDegree[nextCourse]--;
                if (inDegree[nextCourse] == 0) deque.offer(nextCourse);
            }
        }
        return numCourses == 0;
    }

    /**
     * 208_实现前缀树
     */
    class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new Trie();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node != null && node.isEnd;
        }

        public boolean startsWith(String prefix) {
            return searchPrefix(prefix) != null;
        }

        private Trie searchPrefix(String prefix) {
            Trie node = this;
            for (int i = 0; i < prefix.length(); i++) {
                char ch = prefix.charAt(i);
                int index = ch - 'a';
                if (node.children[index] == null) return null;
                node = node.children[index];
            }
            return node;
        }
    }

    /**
     * 39_组合总和
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs_39(0, target, candidates, res, path);
        return res;
    }

    private void dfs_39(int i, int left, int[] candidates, List<List<Integer>> res, List<Integer> path) {
        if (left == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (i == candidates.length || left < 0) return;

        dfs_39(i + 1, left, candidates, res, path);

        path.add(candidates[i]);
        dfs_39(i, left - candidates[i], candidates, res, path);
        path.removeLast();
    }

    /**
     * 22_括号生成
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] path = new char[n * 2];
        dfs_22(0, 0, n, res, path);
        return res;
    }

    /**
     * @param i    目前填了多少括号
     * @param left 左括号个数
     */
    private void dfs_22(int i, int left, int n, List<String> res, char[] path) {
        if (i == n * 2) {
            res.add(new String(path));
            return;
        }
        if (left < n) {
            path[i] = '(';
            dfs_22(i + 1, left + 1, n, res, path);
        }
        if (i - left < left) {
            path[i] = ')';
            dfs_22(i + 1, left, n, res, path);
        }
    }

    /**
     * 79_单词搜索
     *
     * @param board
     * @param word
     * @return
     */
    private static final int[][] DIRECTION_79 = new int[][]{{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs_79(i, j, 0, board, words)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs_79(int i, int j, int k, char[][] board, char[] words) {
        if (board[i][j] != words[k]) return false;
        if (k == words.length - 1) return true;
        board[i][j] = 0;
        for (int[] DIRECTION : DIRECTION_79) {
            int x = i + DIRECTION[0];
            int y = j + DIRECTION[1];
            if (x >= 0 && y >= 0 && x < board.length && y < board[0].length && dfs_79(x, y, k + 1, board, words)) {
                return true;
            }
        }
        board[i][j] = words[k];
        return false;
    }

    /**
     * 131_分割回文串
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs_131(0, s, res, path);
        return res;
    }

    /**
     * 考虑 s[i]到 s[n-1]
     */
    private void dfs_131(int i, String s, List<List<String>> res, List<String> path) {
        if (i == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (isPalindrome(s, i, j)) {
                path.add(s.substring(i, j + 1));
                dfs_131(j + 1, s, res, path);
                path.removeLast();
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }

    /**
     * 51_N皇后
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] queues = new int[n];
        boolean[] col = new boolean[n];
        boolean[] diag1 = new boolean[n * 2 - 1];
        boolean[] diag2 = new boolean[n * 2 - 1];
        dfs_51(0, queues, col, diag1, diag2, res);
        return res;
    }

    /**
     * @param r      第r行
     * @param queues 皇后所在列
     * @param col    某一列是否放皇后
     * @param diag1  副对角线，皇后的行号加列号
     * @param diag2  主对角线，皇后的行号减列号
     * @param res    结构集
     */
    private void dfs_51(int r, int[] queues, boolean[] col, boolean[] diag1, boolean[] diag2, List<List<String>> res) {
        int n = col.length;
        if (r == n) {
            List<String> board = new ArrayList<>();
            for (int queue : queues) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                row[queue] = 'Q';
                board.add(new String(row));
            }
            res.add(board);
            return;
        }
        /*
          在(r,c)上放皇后
         */
        for (int c = 0; c < n; c++) {
            int rc = r - c + n - 1;
            if (!col[c] && !diag1[r + c] && !diag2[rc]) {
                queues[r] = c;
                col[c] = diag1[r + c] = diag2[rc] = true;
                dfs_51(r + 1, queues, col, diag1, diag2, res);
                col[c] = diag1[r + c] = diag2[rc] = false;
            }
        }
    }
}
